//题目:
// 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
// 除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，
// 聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 
// 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

// 给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
#include<iostream>
#include<vector>
#include<map>

using namespace std;
//代码
//  * Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution 
{
    map<pair<TreeNode*,bool>,int> dp;//备忘录
public:
    //返回值是：从 root 结点到叶结点，所有路径上不相邻结点最大和
    int dfs(TreeNode* root,bool flag)
    {
        if(root==nullptr) return 0;

        if(dp.count({root,flag})) return dp[{root,flag}];//记忆化搜索

        int ret1=0,ret2=0;
        //a. root能偷的情况下，偷root结点的情况下能偷多少钱？
        if(flag==true) 
        {
            
            ret1+=root->val;
            ret1+=dfs(root->left,0);
            ret1+=dfs(root->right,0);
        }
        //b. 不偷root结点的情况下，又能偷多少钱？
        ret2+=dfs(root->left,1);
        ret2+=dfs(root->right,1);

        dp[{root,flag}]=max(ret1,ret2);//记忆功能

        return max(ret1,ret2);
    }
    int rob(TreeNode* root) 
    {
        //记忆化搜索   √
        return dfs(root,1);
    }
};